\chapter{Creating game levels}
\label{chap:creatingGameLevels}

One of our aims was to easy the task of the level designers and generate some of the player challenges automatically. In this section we describe our methods of finding solutions of function $F$ from chapter~\ref{chap:problemDefinition}.

In our design process, the designer specifies the initial state of the world $S_{init}$ and number of pitfalls $n \in \mathbb{N}$. $S_{init}$ contains a fully specified map of the level $M$. $M$ remains fixed in the design process; however, the set of entities $E$ and theirs assignment to rooms $EtoR$ and doors' resp. objects' states ($Ds$ resp. $Os$) can be modified. The burglar does not have to know about all these objects and guards. The output of the design process is the real state of the world observable by the player, $S_{real}$, the state known to the burglar, $S_{burglar}$, and a number of successfully assigned pitfalls $k \leq n$. $k$ is less than $n$ if the algorithm fails to add all the required pitfalls.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Generator algorithms} 
\label{sec:generatorToom}

The key to our automated level design is to correctly select the trap rooms. If accomplished, the exact trap types can be easily selected, the exact algorithm we describe in section~\ref{section:trapsToObjects} and the rest of the section will describe our room selecting methods.

Through the development we tried several different approaches, but most of them proved to be inappropriate for our purposes. We can categorize our methods into two groups: One that \emph{leads the burglar agent into a trap}; and one that \emph{places the traps in the agent's path}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Leading the agent into traps}
\label{subs:leadingIntoTrap}

In one type of experiment we tried to randomly generate a trap layout, then through the gameplay lead the burglar through them.

There were two problems with this approach; one from the point of gameplay and a technical one. 

Laying out the traps and forcing the burglar to them may result in unrealistic paths. Sometimes an agent made an obviously useless loop just to stumble into a dangerous situation. These situations may be avoided by either limiting the possible layouts or the places in it that can be used as trap rooms. For example we can't allow the agent to discover shortcuts, the level between each perilous situation must be linear.

The second problem with the method we called \emph{counting traps}. As the burglar moves through the level at each replanning we had to know which trap was still ahead to be visited and which one was already avoided. Deciding whether a trap was successfully avoided while the agent has still not reached its final goal is a surprisingly hard task.
Traps can be disabled in two basic ways -- disabling the object that would catch the burglar, which can be obviously checked, or by evading the room containing it, which is significantly harder to spot. We attempted to solve this problem using 3 different approaches: \emph{comparing plan lengths}, \emph{directly searching for unnecessary room entries}, \emph{checking the existence of a plan without being caught}.

The basic idea behind all three methods is to discover whether the burglar made some actions thats only point is to get caught. In our game such actions manifest as entering the trap room then returning to the previous room without executing any other significant action (one changing the world state $S^M$ as defined in chapter~\ref{chap:problemDefinition}).

\emph{Comparing plan lengths}: if we had optimal planners (as always in the thesis performance is meant as action sequence length) than we could requested a plan through the trap to the agent's goal and another one without it. If the second sequence was shorter we would know, that the player has already avoided the trap therefore we should not include it in future planning runs. Unfortunately, we don't have assurance that the generated plans are optimal, thus the method can't guarantee correct trap creation.

\emph{Directly searching for the unnecessary room entries}: In this method we would have been looking for the actual entering and leaving action sequence in the selected trap room. In practice this method was not implemented because we abandoned the whole principle of leading the burglar into a trap. 

\emph{checking the existence of a plan without being caught}: The third and last method we have implemented in the early versions of the level generator. We were comparing a plan generated with the explicit prohibition of the trap room and the one that contained neither prohibition, nor requirement to enter the trap. If the resulted plans matched, we concluded that the observed trap was avoided.

In the final version we completely abandoned this solution. Our methods of checking the avoidance of traps have frequently failed if applied on more than a single trap and the resulted agent behavior was far from believable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Placing traps on the agent's path}

The other approach we tried and proved to be a reliable was to organize the traps around the burglar's path instead of changing it.

In the following we describe two algorithms we used in the generator to construct game levels and a further improvement we proposed.

The default design algorithm described in Algorithm~\ref{alg:levelDesignCombinations} generates trap rooms that can be avoided without truly disabling them by the player. It uses the planner to determine the expected action sequence $P$ of the burglar in $S_{init}$ that reveals the set of rooms the agent plans to visit. In the next step, it filters out the rooms that the burglar is unable to avoid, like graph choke points, or rooms that hold objects necessary for completion of the burglar's mission; these rooms will not contain traps and the rest of the rooms we call \emph{possible trap rooms}. From this reduced set it generates all subsets with the size smaller or equal to the requested number of traps. Finally it uses the planner to find the largest of these subsets that can be removed from $S_{init}$ while there still exists a $P'$ plan solving the  $S_{reduced}$ reduced map. If such subset is found, it can be returned as the set of trap rooms.

The reason why such a design method works is based on the deterministic behavior of the used planner. After diverting from his original plan and thus avoiding a single trap, the agent will try to return to his original path. This of course presumes that the planner used at the design time is the same as the one used through out the gameplay itself.

\algsetup{indent=2em}
%\newcommand{\factorial}{\ensuremath{\mbox{\sc Evolution}}}
\begin{algorithm}[H]
  \caption{Level design using combinations}
  \label{alg:levelDesignCombinations}
  \begin{algorithmic}[1]
    
    \REQUIRE $S_{init}$ --- initial world state by the designer
    \REQUIRE $n$ --- number of required pitfalls in the level
    \ENSURE trap rooms are assigned to the world state
    
    \STATE $P \leftarrow$ createPlan($S_{init}$)
    \STATE $rooms \leftarrow$ allRoomsIn($P$)
    \STATE $possibleTrapRooms \leftarrow rooms \setminus$ unavoidableRoomsIn($P$)
    
    \FOR{$k=n$ \TO 1 }
      \FORALL{$trapRooms \subseteq possibleTrapRooms \wedge |trapRooms| = k$}
        \STATE $S_{reduced} \leftarrow S_{init}$ without $trapRooms$ in layout
        \IF{$\exists P': P' =$ createPlan($S_{reduced}$)}
          \STATE $S_{real} \leftarrow S_{init}$ with traps in $trapRooms$
          \STATE $S_{burglar} \leftarrow S_{init}$ without traps in $trapRooms$
          \RETURN $\langle S_{real}, S_{burglar}, k \rangle$
        \ENDIF
      \ENDFOR
    \ENDFOR
    
    \RETURN $failure$

  \end{algorithmic}
\end{algorithm}

\algsetup{indent=2em}
%\newcommand{\factorial}{\ensuremath{\mbox{\sc Evolution}}}
\begin{algorithm}[H]
  \caption{Level design using incremental trap creation}
  \label{alg:levelDesignIncremantal}
  \begin{algorithmic}[1]
    
    \REQUIRE $S_{init}$ --- initial world state by the designer
    \REQUIRE $n$ --- number of required pitfalls in the level
    \ENSURE trap rooms are assigned to the world state
    
    \STATE $S_{world} \leftarrow S_{init}$
    \STATE $trapRooms \leftarrow emptySet$ 
    
    \FOR{$k=1$ \TO $n$ }
      \STATE $P \leftarrow$ createPlan($S_{world}$)
      \STATE $rooms \leftarrow$ allRoomsIn($P$)
      \STATE $possibleTrapRooms \leftarrow rooms \setminus$ unavoidableRoomsIn($P$)
      
      \REPEAT
        \STATE $trapRoom \leftarrow$ selectOneFromTheBeginning($possibleTrapRooms$)
        \STATE $S_{reduced} \leftarrow S_{init}$ without $trapRoom$ in layout
      \UNTIL{\NOT $\exists P': P' =$ createPlan($S_{reduced}$)}
      
      \STATE $trapRooms \leftarrow$ insert($trapRooms, trapRoom$)
      \STATE $followingRoom \leftarrow$ followingRoom($possibleTrapRooms, trapRoom$) 
      \STATE $S_{world} \leftarrow S_{world}$ without ($possibleTrapRooms \setminus \{followingRoom\}$)
      \STATE $S_{world} \leftarrow$ moveBurglarTo($S_{world}, followingRoom$)
    \ENDFOR
    
    \STATE $S_{real} \leftarrow S_{init}$ with traps in $trapRooms$
    \STATE $S_{burglar} \leftarrow S_{init}$ without traps in $trapRooms$
    \RETURN $\langle S_{real}, S_{burglar}, n \rangle$
  \end{algorithmic}
\end{algorithm}

\clearpage
Our improved attempt to generate trap rooms is visualized in Algorithm~\ref{alg:levelDesignIncremantal}. 

In a single step of trap selection the method generates a room sequence and choses a single avoidable one that appends to the list of traps; then it places the burglar after the generated trap and prevents him from continuing on the same path that was planned before. This step is repeated until all the requested traps are successfully placed.

For the sake of simplicity the algorithm we presented presumes that it is possible to insert $n$ traps into the layout; furthermore there are $n$ distinct, but interconnected paths leading to the burglar's aim, that are not necessarily true. The one used in practice must cope with these possibilities, but it is based on the same principle.

The main differences between the two algorithms are manifested in performance and in gameplay experience. The first one has exponential time complexity based on the length of the burlgar's path (its execution takes about 5-10 minutes on the test machine); it goes through all the possible room combinations until a sufficient one is reached. The other one must cope with the possibility that by selecting the first several rooms in an inefficient way may leave no place to put the rest of the traps.

The second important difference is in the user impression. The first method results in traps chained in distinct line while the rest of the world is safe. The second algorithm places traps in a more even and less predictable fashion. On the other hand Algorithm 2 requires the game itself to be aware of the fact that it must invalidate the burglar's future plans whenever replanning is necessary.

In practice both algorithms -- the second one to a greater extent -- suffer from the possibility that the player may change the environment in an unexpected way avoiding all the placed traps in a single clever stroke. Whether allowing this possibility is a bug or a feature depends on the reader.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Trap rooms to game objects}
\label{section:trapsToObjects}

We solved the translation of trap rooms to game objects in a very simple fashion. We have two types of objects that are perilous to the burglar: cameras and guards.

Cameras are static, they can be placed into any room to turn it into a trap.

Guards on the other hand are mobile, so a single one may cover multiple neighboring rooms. Their weakness is planning in time; their decision making (a planning system) acts as if the world was a static environment. To avoid leaving rooms temporarily unprotected and letting the burglar slip through without the player's intervention we defined guard territories in a way that every room in them would lay on the path of the burglar as visualized on figure~\ref{fig:guardPlacement}.

We examine each designated trap room, if it has no neighboring dangers we place there a single camera, otherwise we add it to the closest guards territory.

\begin{figure}
	\begin{center}
	\includegraphics[width=75mm]{../img/guardPlacement.eps}
	\end{center}	
	\caption{Selecting guard territory:\\
           a) rooms hard to slip through unnoticed -- ideal for guard territory\\
           b) rooms easy to slip through unnoticed\\
           c) the burglar's path\\
           d) a single room
          }
	\label{fig:guardPlacement}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Replanning behavior and level creation}
\label{sec:replanningAndLevelCreation}

Our agents' planning behavior was described in section~\ref{sec:whenTochangePlans}. The reason to prefer the strategy of pure failure replanning is in the method of our level creation. As we described above, we were examining the future path of the burglar using a single planning process and build our pitfalls around it. 

Giving the agent more freedom to reconsider its actions than absolutely necessary is making the trap placement harder. To maintain correctness we had to simulate the whole agent path with discovering new pieces of information and the same replanning strategy as the one used in the gameplay; however it still wasn't visibly better than the single planning method. The problem was that we have failed to cope with all the possible actions of the player and the ways that may directly or indirectly change the behavior of our agents (for example locking different combination of doors, or influencing other agents that in turn influence each other, \dots). Instead of a single world simulation we would have needed a full world state tree of states $\mathcal{S^M}$ that is branching by the possible user actions from each state $S^M$. 

Such an extensive spatial search was beyond the reach of our thesis, so in the final version we use the simplest of the above methods, the single planning run. To reinforce the validity of its resulted levels in the gameplay previous versions of the program even prohibited the agents to look around and discover their environment so they wouldn't find unknown shortcuts; later however this feature was returned to the gameplay because it greatly enriches the player's possibilities.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}

In the development process we soon realized that our tested planning systems are not producing optimal action sequences, deviation from the minimal number of required actions changes based on the current problem and the used tool. Furthermore some details in our agent guidance (detailed in sections \ref{subs:suboptimalPlanning} and \ref{subs:planningGranularity}) makes our level creation vulnerable to seemingly insignificant implementation details of the planners (for example choosing between equivalent paths or action ordering, \dots) 

At first we tried to request multiple solutions from the planners and at least select the best solution from the results, but we found this process time consuming and superfluous. We do not need the planning systems to produce optimal action sequences only that their new plans are consistent with the previous ones. This can be achieved by using the same tool in both the level generation and through out the gameplay.

Finally we must note that all the above described algorithms are producing traps that are in principle avoidable. In the later stages of the development we introduced user actions that can simply disable them and the burglar needs no route around them. Our program is a puzzle game, there is very little player challenge in disabling unavoidable traps, so the creation of such traps had no priority in our work and ultimately it was left to the human designer.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Running the level generator}

Our program requires a \emph{Java} executing environment; it can be started as a shell script. For the list of accepted parameters see Appendix~\ref{chap:runningTheGenerator}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



